package com.wk.springboot.tree;

import java.util.Comparator;
import java.util.Objects;
import java.util.function.Consumer;

/**
 * 封装tree
 */
public class MyTree<V> {

    /**
     * mytree的根节点
     */
    private Node<V> root;

    //要有一个比较器
    private final Comparator<? super V> comparator;


    public MyTree() {
        this(null);
    }

    public MyTree(Comparator<? super V> comparator) {
        this.comparator = comparator;
    }

    public void add(V v){
        Node<V> node = root;
        if(root == null){
            root = new Node<>(v,null);
        }else {
            int cmp;
            Node<V> parent;
            if(comparator != null){
                do {
                    parent = node;
                    cmp = comparator.compare(node.value,v);
                    if(cmp >= 0){
                        node = node.right;
                    }else {
                        node = node.left;
                    }
                }while(node != null);
            }else {
                @SuppressWarnings("unchecked")
                Comparable<? super V> comparable = (Comparable<? super V>)v;
                do {
                    parent = node;
                    cmp = comparable.compareTo(node.value);
                    if(cmp >= 0){
                        node = node.right;
                    }else {
                        node = node.left;
                    }
                }while(node != null);
            }
            node = new Node<>(v,parent);
            if(cmp >= 0){
                parent.right = node;
            }else {
                parent.left = node;
            }
        }
    }

    /**
     * 遍历这个tree
     * 用jdk8中的四大核心接口之一的consumer接口
     * @param action
     */
    public void forEach(Consumer<? super V> action){
        Objects.requireNonNull(action);

        for(Node<V> node = getFirstNode(); node != null ; node = successor(node)){
            action.accept(node.value);
        }
    }

    /**
     * 前序遍历所有的数据
     * @param node
     * @return
     */
    private Node<V> successor(Node<V> node) {

        if(node == null){
            return null;
        }

        if(node.right != null){
            Node<V> cNode = node.right;
            while(cNode.left != null){
                cNode = cNode.left;
            }
            return cNode;
        }else {
            Node<V> pNode = node.parent;
            Node<V> cNode = node;
            while (pNode != null && pNode.right == cNode){
                cNode = pNode;
                pNode = pNode.parent;
            }
            return pNode;
        }
    }

    /**
     * 获得第一个节点
     * @return
     */
    private Node<V> getFirstNode(){

        Node<V> parent = root;
        if(parent == null){
            return null;
        }
        while (parent.left != null){
            parent = parent.left;
        }
        return parent;
    }

    private final static class Node<V>{

        V value;
        Node<V> left;
        Node<V> right;
        Node<V> parent;

        public Node() {
        }

        public Node(V value, Node<V> parent) {
            this.value = value;
            this.parent = parent;
        }
    }

}
